/*
day233
2020.4.17
*/ 
#include<iostream>
#include<vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int N) {
    	vector<TreeNode *> res;
    	if(N<=0)
    	{
    		return res;
		}
        return help(N);
    }
    
    vector<TreeNode *> help(int N)
    {
    	vector<TreeNode *> res;
    
    	if(N<=0)
    	{
    		res.push_back(nullptr);
    		return res;
		}
		
		
		for(int i=0;i<=N-1;++i)
		{
			vector<TreeNode *> l=help(i);
			vector<TreeNode *> r=help(N-1-i);
			
			for(int p=0;p<l.size();++p)
			{
				for(int q=0;q<r.size();++q)
				{
					if( (l[p]==nullptr && r[q]==nullptr) ||  (l[p]!=nullptr && r[q]!=nullptr)  ) 
					{
						TreeNode *root=new TreeNode(0);
			
						root->left=l[p];
						root->right=r[q];
						
						res.push_back(root);
					}
							
				}
			}
		}
		return res;
	}
};


int main()
{
	return 0;
}
